package medium三数之和;

import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> twoSum(int[] nums, int target){

        List<List<Integer>> num = new ArrayList<>();

        for (int i = 0,j = nums.length-1; i< nums.length;i++) {
            if (i>0 &&nums[i] == nums[i-1]){
                continue;
            }
            while (i < j && nums[i] + nums[j] +target> 0) {
                --j;
            }
            if (i == j) {
                break;
            }
            if (target + nums[i] + nums[j] == 0){
                List<Integer> num1 = new ArrayList<>();
                num1.add(target);
                num1.add(nums[i]);
                num1.add(nums[j]);
                num.add(num1);
            }
        }
//        for(int i=0; i<nums.length-1; i++)
//            for (int j = i; j < nums.length-1; j++) {
//                if (target + nums[i] + nums[j+1] == 0){
//                    List<Integer> num1 = new ArrayList<>();
//                    num1.add(target);
//                    num1.add(nums[i]);
//                    num1.add(nums[j+1]);
//                    num.add(num1);
//                }
//            }
        return num;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> list2 = twoSum(Arrays.copyOfRange(nums,i+1,nums.length),nums[i]);
            if (!list2.isEmpty()){
                for (List<Integer> l: list2) {
                    if (!list.contains(l))
                        list.add(l);
                }
            }
        }
        return list;
    }
    @Test
    public void test(){
        int[] num = {-1,0,1,2,-1,-4,-2,-3,3,0,4};
        Arrays.sort(num);
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i]  );
        }
        List<List<Integer>> list = threeSum(num);
        System.out.println(list.toString());
    }
}
